// Created by WXX on 2021/10/25 9:20
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {

        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;  // 从右上角开始遍历
        while (i < n && j >= 0) {
            int t = matrix[i][j];
            if (t == target) return true;
            if (t < target) i++;
            else j--;
        }
        return false;
    }
};

int main() {

    vector<vector<int>> matrix = {
            {1, 4, 7, 11, 15},
            {2, 5, 8, 12, 19},
            {3, 6, 9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30}
    };
    cout << Solution().searchMatrix(matrix, 5) << endl;  // true

    return 0;
}
